package org.algorithm.熊猫.链表;

import org.algorithm.common.ListNode;
import org.junit.Test;

/**
 * @Date 2022/2/18
 * @Link {https://leetcode-cn.com/problems/aMhZSa/}
 */
public class 回文链表 {

    @Test
    public void test() {
        ListNode node = ListNode.build(1, 2, 2, 2, 1);
        ListNode.print(node);
        System.out.println();

        System.out.println(isPalindrome(node));
    }


    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode last = head;

        //反转节点记录
        ListNode trunNode = null;
        //快慢指针判断中间节点 -同时反转之前节点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            //反转链表
            ListNode cur = last.next;
            last.next = trunNode;
            trunNode = last;
            last = cur;
        }
        //奇偶中间点判断
        if (fast != null) {
            last = last.next;
        }

        //两边循环判断
        while (last != null) {
            if (trunNode.val != last.val) return false;
            last = last.next;
            trunNode = trunNode.next;
        }
        return true;
    }
}
